package 回溯;

import java.util.*;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 单词拆分II140.java
 * @createTime 2023年01月07日 14:05:00
 */
public class 单词拆分II140 {
	List<String> result=new ArrayList<>();
	Set<String> stringSet=new HashSet<>();
	public List<String> wordBreak(String s, List<String> wordDict) {
		stringSet=new HashSet<>(wordDict);
		backTrace(s,0);
		return result;
	}

	LinkedList<String> temp=new LinkedList<>();
	public void backTrace(String s,int curIndex){
		//到了最后
		if (s.length()==curIndex){
			result.add(String.join(" ",temp));
			return;
		}
		for (int i = curIndex; i < s.length(); i++) {
			String str=s.substring(curIndex,i+1);
			if (!isValid(str)){
				continue;
			}
			temp.add(str);
			backTrace(s,i+1);
			temp.removeLast();
		}
	}

	public boolean isValid(String str){
		if (stringSet.contains(str)){
			return true;
		}
		return false;
	}
}
